package com.hoppinzq.algorithm.graph;

import com.hoppinzq.algorithm.stackAndQueue.MyQueue;

/**
 * 2
 * 深度优先遍历
 * 优先遍历各个顶点的子节点
 */
public class DepthFirstSearch {

    private boolean[] marked;//指定节点是否被搜索过，已搜索过为true
    private int count;//跟指定顶点的连通的顶点个数

    /**
     * 搜索指定顶点的连通的顶点
     * @param graph
     * @param v
     */
    public DepthFirstSearch (MyGraph graph,int v){
        this.marked=new boolean[graph.V()];
        this.count=0;
        dfs(graph,v);
    }

    /**
     * 深度优先搜索
     * @param graph
     * @param v
     */
    private void dfs(MyGraph graph,int v){
        //先把v对应的顶点的“是否搜索”置为已搜索。
        marked[v]=true;
        MyQueue<Integer> myQueue=graph.getQueue(v);
        for (Integer c : myQueue) {
            if(!marked(c)){
                dfs(graph,c);
            }
        }
        count++;
    }

    /**
     * 指定顶点w是否与v顶点连通？
     * @param w
     * @return
     */
    public boolean marked(int w){
        return marked[w];
    }

    /**
     * 返回指定顶点连通的顶点数目
     * @return
     */
    public int getCount(){
        return count;
    }
}
